// 2025/10/27
// 查找和最小的k对数字

class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        auto cmp = [&nums1, &nums2](const pair<int, int>& a, const pair<int, int>& b){
            return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        vector<vector<int>> ans;
        int n1 = nums1.size(), n2 = nums2.size();

        for(int i = 0; i < n1; i++)
        {
            pq.emplace(i, 0);
        }
        while(k--)
        {
            auto [pos1, pos2] = pq.top();
            pq.pop();
            ans.emplace_back(initializer_list<int>{nums1[pos1], nums2[pos2]});
            if(pos2 + 1 < n2)
                pq.emplace(pos1, pos2 + 1);
        }
        return ans;
    }
};